home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / Libraries / Advanced I⁄O v2.3 / Advanced i⁄o / arithm_modadapt.cc < prev    next >
Text File  |  1995-05-29  |  6KB  |  179 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /*
  3.  ************************************************************************
  4.  *
  5.  *               Adaptive Arithmetic Coding
  6.  *                 Adaptive model for the data source
  7.  *
  8.  * This is the implementation of the adaptive model based on the
  9.  * Input_Data_Model.
  10.  *
  11.  * The present model is tailored to coding node values of the Laplacian 
  12.  * pyramid decomposition of gray-scale still images. The distribution of
  13.  * the values is found (see laplpyr_hist.lst) to be almost ideally
  14.  * modelled by the Lorentzian distribution with a very strong peak at
  15.  * 0. This apriori information is coded into the frequency tables. As
  16.  * symbols are processed, the frequency tables are updated (in the
  17.  * way it is described in the book "Text Compression" referred to
  18.  * elsewhere) to finely adjust the distribution. Note that re-scaling
  19.  * of the frequencies is carried out more frequently than it is really
  20.  * needed to prevent overflow in the coder. The reason is, rescaling of the 
  21.  * model makes it gradually forget what happened long ago, and tunes in the
  22.  * model to the recent data. It makes sense if the ideal source model changes
  23.  * with the time. It is certainly the case in the Laplacian pyramid,
  24.  * where probability ditribution for different layers may be different.
  25.  *
  26.  * The program assumes the total no. of distinct input symbols
  27.  * (integers) is relatively small, so simple linear arrays can be used
  28.  * for storing and looking up the frequency tables. 
  29.  *
  30.  * $Id: arithm_modadapt.cc,v 1.3 1993/06/24 14:54:07 oleg Exp oleg $
  31.  *
  32.  ************************************************************************
  33.  */
  34.  
  35. #pragma implementation "arithm_modadapt.h"
  36. #include "arithm_modadapt.h"
  37. #include "std.h"
  38.  
  39. /*
  40.  *------------------------------------------------------------------------
  41.  *            Constructors and Destructors
  42.  */
  43.  
  44.                 // Constructor
  45. AdaptiveModel::AdaptiveModel(const Symbol lwb, const Symbol upb)
  46.      : symbol_lwb(lwb), symbol_upb(upb),
  47.        no_symbols(upb-lwb+1)
  48. {
  49.   assure(no_symbols > 1,
  50.      "Bracketing interval for input symbols should include at least "
  51.      "two symbols");
  52.   allocate_model(no_symbols);
  53.   symbol_to_index = new Index[no_symbols];
  54.                 // Note, indices range from 1 to EOF_index,
  55.                 // but EOF_index maps to no symbol
  56.   index_to_symbol = new Symbol[no_symbols];
  57.  
  58.   initialize_model();
  59. }
  60.  
  61.                 // Destructor
  62. AdaptiveModel::~AdaptiveModel()
  63. {
  64.   assert( symbol_to_index != 0 && index_to_symbol != 0 );
  65.   delete [] symbol_to_index;
  66.   delete [] index_to_symbol;
  67. }
  68.  
  69.                 // Initialize the model
  70. void AdaptiveModel::initialize_model(void)
  71. {
  72.                 // Set up the index vs. symbol mapping such
  73.                 // that symbol 0 would have index 1,
  74.                 // symbol 1 - index 2, symbol -1 - index 3,
  75.                 // etc.
  76.   register int i;
  77.                 // Assume the symbol just in the middle is
  78.                 // most likely to occur
  79.   register Symbol symbol  = (symbol_lwb + symbol_upb)/2;
  80.   register Index index;
  81.   for(index=1,i=1; ;)
  82.   {
  83.     assert( symbol >= symbol_lwb && symbol <= symbol_upb );
  84.     symbol_to_index[symbol-symbol_lwb] = index;
  85.     index_to_symbol[index-1] = symbol;
  86.  
  87.     if( !(++index <= no_symbols) )
  88.       break;
  89.  
  90.     while( abs(i) < 2*no_symbols )
  91.     {
  92.       symbol += i;
  93.       i = ( i>0 ? -i-1 : -i+1 );
  94.       if( symbol <= symbol_upb && symbol >= symbol_lwb )
  95.     break;
  96.     }
  97.     assert( abs(i) < 2*no_symbols );
  98.   }
  99.  
  100.                     // Assign initial frequency counts
  101.                     // according to Lorentzian ditribution
  102.   cum_frequencies[no_indices] = 0;
  103.   for(i=no_indices; i>0; i--)
  104.   {
  105.     frequencies[i] = ( i == 1 ? 10*no_symbols : i <= 10 ? 10 : 1 );
  106.     cum_frequencies[i-1] = cum_frequencies[i] + frequencies[i];
  107.   }
  108.   frequencies[0] = 0;            // Must be zero to differ from freq[1]
  109. }
  110.  
  111. /*
  112.  *------------------------------------------------------------------------
  113.  *              Searching for index/symbol
  114.  */
  115.  
  116.                 // Return the index of a given symbol
  117. Index AdaptiveModel::get_index(const Symbol symbol) const
  118. {
  119.   if( symbol < symbol_lwb || symbol > symbol_upb )
  120.     _error("Symbol %d is out of interval [%d,%d]",
  121.        symbol, symbol_lwb, symbol_upb);
  122.   return symbol_to_index[symbol-symbol_lwb];
  123. }
  124.  
  125.                 // Return the symbol for a given index
  126. Symbol AdaptiveModel::get_symbol(const Index index) const
  127. {
  128.   if( index < 1 || index > no_symbols )
  129.     _error("Index %d is out of boundaries [1,%d]",index,no_symbols);
  130.   return index_to_symbol[index-1];
  131. }
  132.  
  133. /*
  134.  *------------------------------------------------------------------------
  135.  *            Update the adaptive model
  136.  *        to account for occurence of a particular index
  137.  */
  138.  
  139. void AdaptiveModel::update_model(const Index index)
  140. {
  141.   if( total_cum_freq() >= Top_freq/4 )    // See if freq counts near their max
  142.   {                    // /4 makes rescaling work more often
  143.     register int cum = 0;        // If so, halve all the counts
  144.     register int i;            // keeping them nonzero, and
  145.     for(i=no_indices; i>=0; i--)    // recompute the cumulative counts
  146.     {
  147.       cum_frequencies[i] = cum;
  148.       cum += (frequencies[i] = (frequencies[i]+1) >> 1);
  149.     }
  150.   }
  151.                     // Try to pull 'index' to the beginning
  152.                     // of the freq. table, skipping symbols
  153.                     // with the same freq.
  154.   register Lword * fp;
  155.   for(fp = &frequencies[index]; *fp == *(fp-1); fp--)
  156.     ;                    // Note, freq[0] never = freq[1]
  157.   Index new_index = fp - frequencies;    // Find a new position for the index
  158.   if( new_index < index )        // If the index is to move, update
  159.   {                    // the translation tables
  160.     Symbol symbol_oind = index_to_symbol[index-1];
  161.     Symbol symbol_nind = index_to_symbol[new_index-1];
  162.     index_to_symbol[index-1] = symbol_nind;
  163.     index_to_symbol[new_index-1] = symbol_oind;
  164.     symbol_to_index[symbol_oind-symbol_lwb] = new_index;
  165.     symbol_to_index[symbol_nind-symbol_lwb] = index;
  166.   }
  167.  
  168.                     // Note, the increment is large enough,
  169.   const int update_inc = no_symbols/5 + 1; // since the count 1 acts like
  170.                     // -Infinity
  171.   frequencies[new_index] += update_inc;    // Increment the freq count for index
  172.   register Lword * cfp;            // And update the cumulative counts
  173.   for(cfp=&cum_frequencies[new_index]; cfp>&cum_frequencies[0]; )
  174.     *--cfp += update_inc;
  175. }
  176.  
  177.  
  178.  
  179.